package com.practice.tree;

import com.practice.util.BinaryTree;
import com.practice.util.BinaryTreeNode;

/**
 * Find largest BST in a binary tree (including all descendants). 
 */
public class LargestBST {
	/**
	 * Returns nodes number of largest BST subtree.
	 * @param tree
	 * @return
	 */
	public int find(BinaryTree tree) {
		return find(tree.getRoot()).maxBST;
	}
	
	private Result find(BinaryTreeNode node) {
		if (node == null) return new Result(0, 0, 0, 0);
		
		if (node.left()==null && node.right()==null) {
			return new Result(node.value(), node.value(), 1, 1);
		}
		
		Result left = find(node.left());
		Result right = find(node.right());

		if (node.left() == null) {
			if (right.min <= node.value()) return notBST(left, right);
			return new Result(node.value(), right.max, right.nodes+1, right.nodes+1);
		}
		
		if (node.right() == null) {
			if (left.max >= node.value()) return notBST(left, right);
			return new Result(left.min, node.value(), left.nodes+1, left.nodes+1);
		}
		
		if (left.nodes < 0 || 
				right.nodes < 0 || 
				left.max >= node.value() ||
				right.min <= node.value()) {
			return notBST(left, right);
		}
		else {
			int total = left.nodes + right.nodes + 1;
			return new Result(left.min, right.max, total, total);
		}
	}
	
	private Result notBST(Result left, Result right) {
		int maxBST = Math.max(left.maxBST, right.maxBST);
		return new Result(0, 0, -1, maxBST);
	}
	
	private class Result {
		int		min;
		int		max;
		int		nodes;
		int		maxBST; 	
		
		public Result(int min, int max, int nodes, int maxBST) {
			this.min = min;
			this.max = max;
			this.nodes = nodes;
			this.maxBST = maxBST;
		}
	}
}
